package cn.edu.xjtu.data_structure.chapter01_linearlist.linkedlist;

import cn.edu.xjtu.data_structure.chapter01_linearlist.ListADT;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/9 19:55
 */
public class LinkedList<E> implements ListADT<E> {
    //单链表的定义
    //带有表头结点header node
    private Link<E> head;//头指针
    private Link<E> tail;//尾指针
    protected Link<E> curr;//指向当前元素前驱结点的指针


    private void setUp() {
        tail = head = curr = new Link<>(null);
    }//初始化

    //构造器
    public LinkedList() {
        setUp();
    }

    public LinkedList(int sz) {
        setUp();
    }//忽略size

    @Override
    public void clear() {  //清空所有结点
        head.setNext(null);
        curr = tail = head;
    }

    @Override
    public void insert(E it) {//在当前位置插入元素
        if (curr == null) {
            System.out.println("no current element");
            return;
        } else {
            curr.setNext(new Link(it, curr.getNext()));
            if (tail == curr) {
                tail = curr.getNext();//如果curr是尾部，则tail需要后移
            }

        }

    }

    @Override
    public void append(E it) {//在表的尾部插入元素
        tail.setNext(new Link(it, null));
        tail = tail.getNext();

    }

    @Override
    public E remove() {//删除并返回当前位置的元素值
        if (!isInList()) return null;
        E it = (E) curr.getNext().getElement();
        if (tail == curr.getNext()) tail = curr;//如果是最后一个元素，则要将尾指针前移
        curr.setNext(curr.getNext().getNext());//移除当前元素
        return it;
    }

    @Override
    public void setFirst() {//将当前位置移到开头
        curr = head;
    }

    @Override
    public void prev() {//将当前位置向前移
        if ((curr == null) || (curr == head)) {
            curr = null;
            return;
        }
        Link<E> temp = head;
        while ((temp != null) && temp.getNext() != curr) {
            temp = temp.getNext();//从头开始找，直到指针域指向curr
        }
        curr = temp;
    }

    @Override
    public void next() {//将当前位置往后移
        if (curr != null) curr = curr.getNext();
    }

    @Override
    public void setPosition(int position) {
        curr = head;
        for (int i = 0; (curr != null) && (i < position); i++) {
            curr = curr.getNext();//从头开始找
        }
    }

    @Override
    public void setValue(E it) {//设置当前位置的元素值
        if (!isInList()) {
            System.out.println("no current element");
            return;
        }
        curr.getNext().setElement(it);

    }

    @Override
    public E currValue() {//获取当前位置的元素值
       if(!isInList())return null;
       return (E) curr.getNext().getElement();
    }

    @Override
    public int length() {//获取表的实际大小
        int count=0;
        for (Link temp = head.getNext(); temp!=null ; temp=temp.getNext()) {
            count++;
        }
        return count;
    }

    @Override
    public boolean isInList() {
       return (curr!=null)&&(curr.getNext()!=null);
    }

    @Override
    public boolean isFull() {
        return false;
    }

    @Override
    public boolean isEmpty() {//判断表是否满了
        return head.getNext()==null;
    }

    @Override
    //打印表
    public void print() {
        if (isEmpty()) {
            System.out.println("empty");
        } else {
            System.out.print("(");
            for (setFirst(); isInList(); next()) {
                System.out.print(currValue() + " ");
            }
            System.out.println(")");
        }
    }
}
